package java学习.算法.动态规划;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/15 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 连续子数组的最大和 {
    public static int FindGreatestSumOfSubArray(int[] array) {
        int n = array.length;
        if (n<=1){
            return array[0];
        }
        int sum =0;
        int max =array[0];
        for (int i = 0; i <n ; i++) {
            sum = 0;
            for (int j = i; j < n ; j++) {
                sum+=array[j];
                max = Math.max(sum,max);
            }
        }
        return  max;
    }
    static int x  ,y;
    public static void main(String args[]){
//        x--;
//        myMethod( );
//        System.out.println(x+y+ ++x);

//       int[] array = {1,-2,3,10,-4,7,2,-5};
        int[] array = {-2,-8,-1,-5,-9};
        System.out.println(FindGreatestSumOfSubArray(array));
        System.out.println(FindGreatestSumOfSubArray1(array));
        System.out.println(FindGreatestSumOfSubArray2(array));
        System.out.println(FindGreatestSumOfSubArraydp(array));
        System.out.println(maxSubArray(array));
        System.out.println(Arrays.toString(maxSubArrayAndArray(array)));
        System.out.println(Arrays.toString(Array2(array)));
    }
    public static void myMethod( ){
        y=x++ + ++x;  // -1 + 1 y =0 x = 1
    }

    public  static  int FindGreatestSumOfSubArraydp(int[] array) {
        int n = array.length;
        int[] dp = new int[n];
        int max = array[0];
        dp[0] = array[0];
        for(int i=1;i<n;i++){
            // 动态规划，状态转移方程，确定dp[i]的最大值
            dp[i] = Math.max(dp[i-1] + array[i], array[i]);
            // 每次比较，保存出现的最大值
            max = Math.max(max,dp[i]);
        }
        return max;
    }
    public static int  FindGreatestSumOfSubArray1(int[] array) {
        int n = array.length;
        if (n <= 1) {
            return array[0];
        }
        int res =  process(array,0,0);
        return res;
    }
    public static int  process(int[] array,int index,int cur){
        int n = array.length-1;
        if ( index == array.length){
            return cur;
        }
//        cur = Math.max(cur,0)+array[index];
        cur = cur<=0?array[index]:cur+array[index];
        /*
        当前cur 如果cur+之后的值之后<0 ，说明不对，需要舍弃，注意是求连续的！！！
        */
        int res =  process(array,index+1, cur); // 选中当前index的值

        return Math.max(res,cur);
    }
    public static int  FindGreatestSumOfSubArray2(int[] array) {
        int n = array.length;
        if (n <= 1) {
            return array[0];
        }
        int [] dp = new int[n]; // 初始化为0
        Arrays.fill(dp, -1);
        int res =  process2(array,0,0,dp);
        return res;
    }
//    记忆化搜索
    public static int  process2(int[] array,int index,int cur,int[] dp){
        if (dp[index]!=-1){
            return dp[index];
        }
        int n = array.length-1;
        if ( index == n+1){
            dp[index] = cur;
            return dp[index];
        }
        cur = cur<=0?array[index]:cur+array[index];
        int res =  process(array,index+1, cur);
        dp[index] = Math.max(res,cur);
        return dp[index] ;
    }
        public  static  int maxSubArray(int[] num) {
            int n = num.length;
            int[] dp = new int[n];
            //边界条件
            dp[0] = num[0];
            int max = dp[0];
            for (int i = 1; i < n; i++) {
                //转移公式
                dp[i] = Math.max(dp[i - 1], 0) + num[i];
                //记录最大值
                max = Math.max(max, dp[i]);
            }
            return max;
        }

    public  static  int[]  maxSubArrayAndArray(int[] array) {
        int n = array.length;
        int[] dp = new int[n];
        //边界条件
        dp[0] = array[0];
        int max = dp[0];
        int start=0,end=0 ;
        int maxstart = 0 , maxend=0 ;
        for (int i = 1; i < n; i++) {
            end++;
            dp[i] = Math.max(dp[i - 1], 0) + array[i];
            if (dp[i-1]+array[i]<array[i]){
                // 此时 连续出现中断，重新来过
                start = end;
            }
            // 若出现更大的区间：或有更大的值
            if (dp[i]>max ||dp[i]==max&&(end-start)>(maxend-maxstart)){
                max = dp[i];
                maxend = end;
                maxstart  = start;
            }

        }
//        找到max之后，确定其数组

        //最后拼接从[start+1,end]区间内的元素
        int[] path = new int[maxend-maxstart+1];
        int index =0;
        for (int i = maxstart; i <= maxend; i++) {
//            path[index++] = array[i];
            path[i-maxstart] = array[i];
        }
        return path;
    }
    public  static  int[] Array2 (int[] array) {
        // write code here
        //方法一 动态规划
        int len = array.length;
        int[] dp = new int[len];
        dp[0] = array[0];
        int max = array[0];
        for(int i=1;i<len;++i){
            dp[i] = Math.max(array[i]+dp[i-1],array[i]);
            max = Math.max(dp[i],max);
        }
        int start=-1,end=len-1,j=len-1;
        //从后往前走，找到第一个等于max的下标
        for(;j>=0;--j){
            if(dp[j]==max){
                end = j;
                break;
            }
        }
        //从j-1下标开始继续 从后往前走，找到第一个比0小的数的下标，如果没有就默认是0
        for(j = j-1;j>=0;--j){
            if(dp[j]<0){
                start = j;
                break;
            }
        }
        //最后拼接从[start+1,end]区间内的元素
        int[] path = new int[end-start];
        int index=0;
        for(int i=start+1;i<=end;++i){
            path[index++] = array[i];
        }
        return path;
    }
}

